package librairies.arborescence.arbre;

import librairies.arborescence.interfaces.IBinarbre;
import librairies.liste.interfaces.IListe;
import librairies.liste.list.ListeDC;

/**
 * arbre binaire en DC
 * 
 * @author mlozach
 * @param <E> type de l'elements dans l'arbre
 */
public class BinarbreDC<E extends Comparable<E>> implements IBinarbre<E> 
{
	private BinarbreDC<E> father;
	private BinarbreDC<E> left;
	private BinarbreDC<E> right;
	private E value;
	private int height;

	public static boolean printBalance;
	
	/**
	 * constructeur par recopie
	 * @param e la valeur de la racine
	 */
	public BinarbreDC(E e) 
	{
		this.father = null;
		this.left = null;
		this.right = null;
		this.value = e;
		this.height = 0;
		
		this.printBalance = false;
	}
	
	/**
	 * permet de faire une suite de charactere.
	 * @param c le charactere a cloner.
	 * @param i le nombre de clone que l'on doit faire.
	 * @return la chaine de caractere.
	 */
	private String seqChar(char c, int i) 
	{
		String res = "";
		
		for(; i > 0; i--)
		{
			res+=c;
		}
		
		return res;
	}
	
	/**
	 * permet d afficher correctement l'arbre.
	 * @param a l arbre a afficher.
	 * @return la liste de niveau.
	 */
	private <F extends Comparable<F>> IListe<String> niveaux(BinarbreDC<F> a) 
	{
		if(a == null) return new ListeDC<String>();
		
		String etiq = a.getVal().toString();
		
		if(this.printBalance)
		{
			etiq += "("+a.balance()+")";
		}
		
		if(a.isLeaf())
		{
			IListe<String> l = new ListeDC<String>();
			l.add(etiq);
			
			return new ListeDC<String>(l);
		}
		
		IListe<String> niveauxL = (a.getLeft()==null ? new ListeDC<String>() : niveaux(a.getLeft()));
		IListe<String> niveauxR = (a.getRight()==null ? new ListeDC<String>() : niveaux(a.getRight()));
		IListe<String> res = new ListeDC<String>();
		
		int largeurL = (niveauxL.size()==0 ? 1 : niveauxL.get(0).length());
		int largeurR = (niveauxR.size()==0 ? -1 : niveauxR.get(0).length());
		
		for(int k = 0; k < niveauxL.size() && k<niveauxR.size(); k++)
		{
			res.add(k, niveauxL.get(k) + " " + niveauxR.get(k));
		}
		
		for(int k = niveauxL.size(); k < niveauxR.size(); k++)
		{
			res.add(k, seqChar(' ', largeurL+1) + niveauxR.get(k));
		}
		
		for(int k = niveauxR.size(); k < niveauxL.size(); k++)
		{
			res.add(k, niveauxL.get(k) + seqChar(' ', largeurR+1));
		}
		
		String traits = (a.getRight() == null ? "|" : "+"+seqChar('-', largeurL)+"+");
		traits += seqChar(' ', largeurL+1+largeurR-traits.length());
		res.add(0, traits).add(0, etiq+seqChar(' ', largeurL+1+largeurR-etiq.length()));
		
		return res;
	}
	
	/**
	 * permet de cree un arbre avec une liste de valeur
	 * @param l la liste de valeur.
	 * @return le nouveau arbre.
	 */
	private BinarbreDC<E> creeArbre(IListe<E> l) 
	{
		if(l == null || l.size() == 0)
		{
			return null;
		}
		
		if(l.size() == 1)
		{
			return buildLeaf(l.get(0));
		}
		
		if(l.size() == 2)
		{
			return (BinarbreDC<E>) buildLeaf(l.get(0)).addVal(l.get(1));
		}
		
		int milieu = l.size()/2;
		BinarbreDC<E> res = buildLeaf(l.get(milieu));
		
		res.left = creeArbre(l.subList(0, milieu-1));
		res.right = creeArbre(l.subList(milieu+1, l.size()-1));
		res.left.father = res;
		res.right.father = res;
		res.updateHeight();
		
		return res;
	}
	
	/**
	 * permet de cree une racine ou une feuille.
	 * @param e le valeur de la feuille.
	 * @return le nouveau sous arbre.
	 */
	private BinarbreDC<E> buildLeaf(E e) {return new BinarbreDC<E>(e);}
	
	/**
	 * permet de mettre a jour la taille et la taille des peres.
	 */
	protected void updateHeight() 
	{
		int bakHeight = height;
		int hg = (left ==null ? -1 : this.left.height);
		int hd = (right==null ? -1 : this.right.height);
		this.height = (hg<hd ? hd : hg) + 1;
		
		if(this.father != null && bakHeight != this.height)
		{
			this.father.updateHeight();
		}
	}
	
	@Override
	public int familySize() 
	{
		return (this.right==null ? 0 : 1+this.right.familySize())+(this.left==null ? 0 : 1+this.left.familySize());
	}
	
	@Override
	public int balance() 
	{
		return (this.right==null ? 0 : 1+this.right.height())-(this.left==null ? 0 : 1+this.left.height());
	}
	
	@Override
	public BinarbreDC<E> ancestor() 
	{
		if(this.father == null)
		{
			return null;
		}
		
		BinarbreDC<E> aieul = this.father;
		
		while(aieul.father != null) aieul = aieul.father;
		
		return aieul;
	}

	@Override
	public BinarbreDC<E> brother() 
	{
		if(this.father == null)
		{
			return null;
		}
		
		if(this.father.left == this)
		{ 
			return this.father.right;
		}
		
		return this.father.left;
	}

	@Override
	public IListe<? extends BinarbreDC<E>> ancestors() 
	{
		IListe<BinarbreDC<E>> res = new ListeDC<BinarbreDC<E>>();
		
		for(BinarbreDC<E> aieul = this.father; aieul != null; aieul = aieul.father)
		{
			res.add(0, aieul);
		}
		
		return res;
	}

	@Override
	public IListe<? extends BinarbreDC<E>> gen(int n) 
	{
		IListe<BinarbreDC<E>> res = new ListeDC<BinarbreDC<E>>();
		
		if(n<1) 
		{
			return res;
		}
		
		if(n==1) 
		{
			if(this.left!=null)
			{
				res.add(this.left);
			}
			
			if(this.right != null)
			{
				res.add(this.right);
			}
			
			return res;
		}
		
		if(this.left != null)
		{
			res.addAll(this.left.gen(n-1));
		}
		
		if(this.right != null)
		{
			res.addAll(this.right.gen(n-1));
		}
		
		return res;
	}

	@Override
	public boolean containsVal(E e) 
	{
		if(e == null)
		{
			return false;
		}
		
		int comparaison=e.compareTo(this.value);
		
		if(comparaison == 0)
		{
			return true;
		}
		
		if(comparaison < 0 && this.left != null)
		{
			return this.left.containsVal(e);
		}
		
		if(comparaison > 0 && this.right != null)
		{
			return this.right.containsVal(e);
		}
		
		return false;
	}
	
	@Override
	public boolean containsAll(IListe<? extends E> liste) 
	{
		if(liste == null || liste.size() == 0)
		{
			return false;
		}
		
		for(int i = 0; i < liste.size(); i++)
		{
			if(!containsVal(liste.get(i)))
			{
				return false;
			}
		}
		
		return true;
	}
	
	@Override
	public E maxVal() 
	{
		if (this.right == null)
		{
			return this.value;
		}
		
		return this.right.maxVal();
	}
	
	@Override
	public E minVal() 
	{
		if (this.left == null)
		{
			return this.value;
		}
		
		return this.left.minVal();
	}
		
	@Override
	public IBinarbre<E> addVal(E e) 
	{
		if(e == null)
		{
			return this;
		}
		
		int comparaison=e.compareTo(this.value);
		
		if(comparaison < 0)
		{
			if(this.left != null)
			{
				this.left.addVal(e);
			}
			
			else 
			{
				this.left = buildLeaf(e);
				this.left.father = this;
				updateHeight();
			}
		}
		
		if(comparaison > 0)
		{
			if(this.right != null)
			{
				this.right.addVal(e);
			}
			
			else 
			{
				this.right = buildLeaf(e);
				this.right.father = this;
				updateHeight();
			}
		}
		
		return this;
	}
	
	@Override
	public IBinarbre<E> addAll(IListe<E> l) 
	{
		if(l == null || l.size() == 0)
		{
			return this;
		}
		
		IBinarbre<E> res = this;
		
		for(int i = 0; i < l.size(); i++)
		{
			res = res.addVal(l.get(i));
		}
		
		return res;
	}
	
	@Override
	public IBinarbre<E> cutVal(E e) 
	{
		if(e == null)
		{
			return this;
		}
		
		int comparaison = e.compareTo(this.value);
		
		if(comparaison == 0) 
		{
			if(this.left != null) 
			{
				BinarbreDC<E> maxLeft = this.left;
				
				while(maxLeft.right != null)
				{
					maxLeft = maxLeft.right;
				}
				
				this.value = maxLeft.value;
				maxLeft.cutVal(maxLeft.value);
			}
			else if(this.right!=null) 
			{ 
				BinarbreDC<E> minRight = this.right;
				
				while(minRight.left != null)
				{
					minRight = minRight.left;
				}
				
				this.value = minRight.value;
				minRight.cutVal(minRight.value);
			}
			else {
				if(this.father != null) 
				{
					if(this.father.left == this)
					{
						this.father.left  =null;
					}
					else
					{
						this.father.right = null;
					}
					this.father.updateHeight();
				}
				
				this.father = null;
				return null;
			}			
		}
		
		if(comparaison < 0 && this.left != null)
		{
			this.left = (BinarbreDC<E>) this.left.cutVal(e);
		}
		
		if(comparaison > 0 && this.right != null)
		{
			this.right = (BinarbreDC<E>) this.right.cutVal(e);
		}
		
		return this;
	}

	@Override
	public IBinarbre<E> cutAll(IListe<E> l) 
	{
		if(l == null || l.size() == 0)
		{
			return this;
		}
		
		IBinarbre<E> candidat = this;
		
		for(int i = 0; i < l.size(); i++)
		{
			candidat=candidat.cutVal(l.get(i));
		}
		
		return candidat;
	}
	
	@Override
	public IListe<E> prefixe() 
	{
		IListe<E> res = new ListeDC<E>().add(this.value);
		
		if(this.left != null)
		{
			res.addAll(this.left.prefixe());
		}
		
		if(this.right != null)
		{
			res.addAll(this.right.prefixe());
		}
		
		return res;
	}

	@Override
	public IListe<E> infixe() 
	{ 
		IListe<E> res = new ListeDC<E>();
		
		if(this.left != null)
		{
			res.addAll(this.left.infixe());
		}
		
		res.add(this.value);
		
		if(this.right != null)
		{
			res.addAll(this.right.infixe());
		}
		
		return res;
	}

	@Override
	public IListe<E> postfixe() 
	{
		IListe<E> res = new ListeDC<E>();
		
		if(this.left != null)
		{
			res.addAll(this.left.postfixe());
		}
		
		if(this.right != null)
		{
			res.addAll(this.right.postfixe());
		}
		
		return res.add(this.value);
	}

	@Override
	public IListe<E> largeur() 
	{ 
		IListe<E> res = new ListeDC<E>().add(this.value);
		int height = height();
		
		for (int n = 1; n <= height; n++) 
		{
			IListe<? extends BinarbreDC<E>> niveaux = gen(n);
			
			for (int i = 0; i < niveaux.size(); i++)
			{
				res.add(niveaux.get(i).value);
			}
		}
		
		return res;
	}
		
	@Override
	public IBinarbre<E> equilibre() 
	{
		BinarbreDC<E> a = creeArbre(infixe());
		
		if(this.left != null)
		{  
			this.left.father = null;
		}
		
		if(this.right != null)
		{ 
			this.right.father = null;
		}
		
		this.value = a.value;
		this.left = a.left;
		this.right = a.right;
		this.height = a.height;
		
		if(this.left != null)
		{  
			this.left.father = this;
		}
		
		if(this.right != null)
		{ 
			this.right.father = this;
		}
		
		return this;
	}
	
	@Override
	public BinarbreDC<E> getFather() {return this.father;}
	@Override
	public E getVal() {return this.value;}
	@Override
	public int height() {return this.height;}
	@Override
	public boolean isLeaf() {return this.left==null && this.right==null;}
	@Override
	public BinarbreDC<E> getLeft() {return this.left;}
	@Override
	public BinarbreDC<E> getRight() {return this.right;}
	@Override
	public void setLeft(BinarbreDC<E> l) {this.left = l;}
	@Override
	public void setRight(BinarbreDC<E> r) {this.right = r;}
	@Override
	public void setFather(BinarbreDC<E> f) {this.father = f; }

	/**
	 * methode Object
	 */
	public String toString() 
	{
		IListe<String> niveaux = niveaux(this);
		String res="";
		
		for(int i = 0; i < niveaux.size(); i++)
		{
			res+=niveaux.get(i)+"\n";
		}
		
		return res;
	}
}